Binary Search

Linear search is slow. Just think of using it by hand with a paper dictionary. Looking up "zebra" would take a long time if you first had to inspect every entry that preceeded it. Usually you search for an entry by guessing about where it will be in the dictionary and then going to that page. If your guess is correct, you are done. Otherwise you refine your guess by looking at the page you picked and deciding if your new guess should go forward or backward. You can do this because the words are in sorted order.

When an array is ordered, an algorithm called binary search can be used to search for an entry. This algorithm works about the same way as you do when you search a dictionary. The Arrays class has several binarySearch() methods that can quickly search arrays of primitive types or of object references. Let us look at the one that searches an array of object references.

static int binarySearch( Object[] array, Object key )

Search the array for an object that matches key, using the compareTo() method. If the object is found, return the index of the object in the array. Otherwise, return a negative value R.

If the return value R is negative, then (-R) is one cell beyond where the key would be found if it were in the array. Use this value to insert a new element into its proper place in the array. (Move elements at (-R) and above to make room.)

If (-R) equals the size of the array, then the key is not in the array, and it should go at the very end, but there is no room.

For now, let us use binary search for searching and not insert new entries into the array.